/*
 MIT License
 
 Copyright (c) 2021 Steven Le

 Permission is hereby granted, free of charge, to any person obtaining a copy
 of this software and associated documentation files (the "Software"), to deal
 in the Software without restriction, including without limitation the rights
 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 copies of the Software, and to permit persons to whom the Software is
 furnished to do so, subject to the following conditions:
 
 The above copyright notice and this permission notice shall be included in all
 copies or substantial portions of the Software.
 
 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 SOFTWARE.					
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
	平面坐标移动开发
	1. 点结构
	2. 面结构
*/

// 坐标结构体
typedef struct __point
{
	struct __point* np;
	// 横坐标
	int px;
	// 纵坐标
	int py;
} point;

// 布尔类型
typedef enum
{
        true=1, 
	false=0
} bool;

const int POINTSTACK_DEFAULT_SIZE = 10;

// 坐标栈结构体
typedef struct __point_stack
{
	// 默认的栈大小
	int capacity;
	// 当前的元素个数
	int pointCount;
	// 链表用于保存栈的点
	struct __point * pl;
	// 栈顶点
	struct __point * top;
} point_stack;

/**
 *	通过坐标的横坐标和纵坐标。
 *   	参数： 	int x 横坐标
		int y 纵坐标 
 * 	返回值：	Point * 点
 */
point * create_point(int x, int y);


/**
 *	打印坐标的值
 *   	参数： 	Point *p 点
 * 	返回值：	无
 */
void print_point(point *p);

/**
 *	由字符串的数据，通过点的移动方式生成链式栈。
 * 	参数： 	char[] str 点移动字符串
 * 	返回值：	point_stack * 字符串中描述的点的移动方式生成的链式栈
 */
point_stack* create_point_stack(char str[]);

/**
 *	向栈中压入节点p。
 * 	参数： 	point_stack *ps  链式栈
 * 		Point *p        压入的点
 * 	返回值：	空
 */
void push_point(point_stack* ps, point *p);

/**
 *	从栈中压入节点p。
 * 	参数： 	point_stack*ps  链式栈
 *      返回值：point *p        压入的点
 * 
 */
point * pop_point(point_stack *ps);

/**
 *	打印栈。
 * 	参数： 	point_stack *ps  链式栈
 * 	返回值：	空
 */
void print_point_stack(point_stack *ps);

/**
 *	释放栈内存空间
 * 	参数： 	point_stack *ps  链式栈
 * 	返回值：	空
 */
void free_stack(point_stack *ps);


/**
 *	判断字符串中是否含有为一个数字
 * 	参数： 	char* token 字符串
 * 	返回值：	bool 0 没有
 * 		      1 有
 */
bool is_number(char * token);

/**
 *	取得字符串的一个子串
 * 	参数： 	char* token 字符串
 * 	返回值：	char* 字符串子串
 * 		      
 */
char * get_substring(char * token);

/**
 *	取得最终的结果并打印
 * 	参数： 	point_stack * ps
 * 	返回值: 空
 * 		      
 */
void get_result(point_stack * ps);

// 主函数
int main()
{
	// 字符串向量（描述点在二维平面上的移动轨迹）
	char str[] = "A10;S20;W10;D30;X;A1A;B10A11;;A10;";
	
	// 创建点栈
	point_stack * ps = create_point_stack(str);
	// 打印点栈
	print_point_stack(ps);

	printf("print pop point\n");
	point *p = pop_point(ps);
	print_point(p);

	// 打印点栈
	print_point_stack(ps);
	// 释放点栈内存空间
	get_result(ps);
	free_stack(ps);
	return 0; 
}

point * create_point(int x, int y)
{	
	point *p = (point *)malloc(sizeof(point)); 
	p->px = x;
	p->py = y;
	return p;
}

void print_point(point *p)
{
	printf("|%d\t|%d\t|\n", p->px, p->py);
}

point_stack * create_point_stack(char str[])
{
	printf("Parsing the input string '%s' \n", str);
	char *token = strtok(str, ";");

	point_stack *ps = (point_stack *)malloc(sizeof(point_stack));
	ps->capacity = POINTSTACK_DEFAULT_SIZE;
	ps->pointCount = 0;
	while(token)
	{
		puts(token);
		point *p;
		// 数值在65和68之间
		if (
		(strlen(token) == 3)		/* token 长度限制为 3*/
		)		
		{
			if (token[0] == 65 && is_number(token))
			{
				// A10
				char *out = get_substring(token);
				printf("move left for %s\n", out);
				p = create_point(-atoi(out), 0);
				push_point(ps, p);
			} 
			
			if(token[0] == 83 && is_number(token)) {
				// S20
				char *out = get_substring(token);
				printf("move down for %s\n", out);
				p = create_point(0, -atoi(out));
				push_point(ps, p);
			}

			if(token[0] == 87 && is_number(token)) {
				// W10
				char *out = get_substring(token);
				printf("move up for %s\n", out);
				p = create_point(0, atoi(out));
				push_point(ps, p);
			} 

			if(token[0] == 68 && is_number(token)) {
				// D30
				char *out = get_substring(token);
				printf("move right for %s\n", out);
				p = create_point(atoi(out), 0);
				push_point(ps, p);
			}
		} else {
			printf("遇到需要跳过的字符串\n");
		}
		token = strtok(NULL, ";");
	}

	return ps;
}

void get_first(char * token)
{
	printf("%c, %d\n", token[0], token[0]);
}

void push_point(point_stack *ps, point *p)
{
	// 栈为空时，直接返回
	if (!ps)
		return;
	// 栈超过容量时，直接返回跳过
	if (ps->pointCount >= ps->capacity)
	{
		printf("stack over capacity");
		return;
	}
	// 取得顶部节点, 顶部节点赋值给
	ps->top = p;
	// 取得链表的头
	point *head = ps->pl;
	// 取得头部节点设置为p
	// printf("%s\n", p->np);
	p->np = head;
	int count = 1;
	while (head != NULL)
	{
		head = head->np;
		count++;
	}
	// 记录
	ps->pl = p;
	ps->pointCount = count;
}

point* pop_point(point_stack *ps)
{
	// 栈为空时，直接返回
	if (!ps) {
		printf("stack is empty \n");
		return NULL;
	}
	
	point *top = ps->top;
	point *toptmp = top;
	top = top->np;
	ps->pointCount--;
	ps->top = top;
	ps->pl = top;
	return toptmp;
}

void print_point_stack(point_stack  *ps)
{
	printf("capacity:%d \n pointCount：%d\n", ps->capacity, ps->pointCount);
	printf("print Point Stack Elements\n");
	point *p = ps->top;
	while (p != NULL)
	{
		print_point(p);
		p = p->np;
	}
	printf("print top of Stack\n");
	print_point(ps->top);
}

bool is_number(char * token)
{
	return token[1] >= 48		
		&& token[1] <= 57
		&& token[2] >= 48
		&& token[2] <= 57;
}

char * get_substring(char * token)
{
	char *dest;
	return memcpy(dest, 
		token + 1 * sizeof(char), 
		3 * sizeof(char));
}

void free_stack(point_stack *ps) 
{
	free(ps);
}

void get_result(point_stack * ps)
{

	point *p = (point *)malloc(sizeof(point));
	int result = 0;
	while(ps->top != NULL)
	{
		p->px += ps->top->px;
		p->py += ps->top->py;
		pop_point(ps);
	}
	printf("----end-----\n");
	print_point(p);
}
